package org.raymond.iworks.study.basic.algorithm.sort;

/**
 * @author raymond
 * @version V1.0
 * @Description: TODO
 * 度量算法执行时间的两种方法
 * 1)事后统计法: end-start.同一台计算机上相同状态下运行
 * 2)事前估算法:
 * 通过分析某个算法的时间复杂度来判断哪个算法更优
 *
 * 时间频度:
 * 一个算法花费的时间与算法中语句的执行次数成正比.哪个算法中语句执行次数多,它花费时间就多.
 * 一个算法中的语句执行次数称为语句频度或时间频度.记为T(n).
 * 时间复杂度:
 * 1)一般情况下,算法中的基本操作语句的重复执行次数是问题规模n的某个函数,用T(n)表示,
 * 若有某个辅助函数f(n),使得当n趋近于无穷大时,T(n)/f(n)的极限值为不等于0的常数,则称
 * f(n)是T(n)的同数量级函数.记作T(n)=O(f(n)),称O(f(n))为算法的渐进时间复杂度,简称时间复杂度.
 *
 * 2)T(n)不同,但时间复杂度可能相同.如:T(n)=n的平方+7n+6与T(n)=3n的平方+2n+2,它们的T(n)不同,
 * 但时间复杂度相同,都是O(n的平方).
 *
 * 3)计算时间复杂度的方法:
 *  * 用常数1代替运行时间中的所有加法常数
 *  * 修改后的运行次数函数中,只保留最高阶项
 *  * 去除最高阶的系数
 *
 *  场景的时间复杂度:
 *  1) 常数阶O(1)
 *  2) 对数阶O(log2n) log以2为底的n的对数
 *  3) 线性阶O(n)
 *  4) 线性对数阶O(nlog2n)
 *  5) 平方阶O(n^2) 双层for循环
 *  6) 立方阶O(n^3) 三层for循环
 *  7) k次方阶O(n^k) k层for循环
 *  8) 指数阶O(2^n)
 *  9) 阶乘 O(n!)
 *  10) O(n^n)
 *  常见时间复杂度有小到大依次为: O(1)<O(log2n)<O(n)<O(nlog2n)<O(n^2)<O(n^3)<O(n^k)<O(2^n),
 *  随着问题规模的不断扩大,上述时间复杂度不断增大,算法的执行效率越低
 *  从图中可见,我们应该尽可能避免使用指数阶的算法
 */

/**
 * 平均时间复杂度和最坏时间复杂度
 * 1) 平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下,该算法的运行时间
 * 2) 最坏情况下的时间复杂度称为最坏时间复杂度.一般讨论的时间复杂度均是最坏啥情况下的时间复杂度.
 * 这样做的原因是:最坏情况下的时间复杂度是算法在任何输入实例上运行时间的界限,这就保证了算法的运行时间
 * 不会比最坏情况更长.
 * 3) 平均时间复杂度和最坏时间复杂度是否一致,和算法有关.
 */
public class TimeComplexityTest {
    /**
     * 时间复杂度,常数阶O(1)
     * 无论代码执行了多少行,只要没有循环等复杂结构,那么代码的时间复杂度就是O(1)
     * 下列代码执行的时候,消耗的时间并不随着某个变量的增长而增长,
     * 那么无论这类代码有多长,即使有几万几十万行,都可以用O(1)来表示它的时间复杂度
     */
    public static void test1(){
        int i=1, j=2;
        ++i;
        j++;
        int m=i+j;
    }
    /**
     * 时间复杂度,对数阶O(log2n)
     * 在while循环里面,每次都将i乘以2,乘完之后,i距离n就越来越近了.假设循环x次后,i大于n,此时这个循环就退出了,也就是
     * 说2的x次方等于n,那么x=log2n,也就是说当循环log2n次以后,这个代码就结束了.因此这个代码的时间复杂度为O(log2n).
     * O(log2n)这个2时间上是根据代码变化的,i=i*3,则是O(log3n)
     * 如果N=a^x(a>0,a!=1),即a的x次方等于N(a>0,且a=1),那么数x就叫做以a为底N的对数,记作x=logaN.
     * 其中,a叫做对数的底数,N叫做真数,x叫做"以a为底N的对数"
     * 对数是指数函数的逆运算.
     */
    public static void test2(){
        int i=1;
        int n=1024;
        while(i<n){
            i=i*2;
        }
        // x=log2的1024
    }

    /**
     * 线性阶,O(n)
     * for循环里的代码会执行n遍,因此它消耗的时间是随着n的变化而变化的.因此这类代码都可以用O(n)来表示时间复杂度
     */
    public static void test3(){
        int j;
        int n=100;
        for(int i=0; i<=n; i++){
            j = i;
            j++;
        }
    }

    /**
     * 线性对数阶O(nlog2n)
     * 将时间复杂度为O(log2n)的代码循环N遍,就是O(n)*O(log2n),也就是O(nlogn)了
     * 注:底数2被忽略了
     */
    public static void test4(){
        int i=0;
        int n=1024;
        for(int m=0; m<n; m++){
            i=1;
            while(i<n){
                i=i*2;
            }
        }
    }
    /**
     * 平方阶O(n^2)
     * 把O(n)的代码再嵌套循环一次,时间复杂度就是O(n^2)
     */
    public static void test5(){
        int j=0;
        int n=100;
        for(int x=1;x<n;x++){
            for(int y=1;y<n;y++){
                j++;
            }
        }
    }
    public static void main(String[] args) {
    }
}
